package com.desheng.bigdata.ds.link;

/**
 * 自定义LinkedList
 * 即双向链表
 * 在操作的过程中一定不要直接拿着head元素和tail进行next/prev的操作，因为是两个标记元素，不能乱动
 */
public class MyLinkedList<E> {

    private Node<E> head;//头结点
    private Node<E> tail;//头结点
    private int size;
    class Node<E> {
        Node prev;//前驱节点
        E data;//当前节点数据
        Node next;//后继节点

        public Node(Node prev, E data, Node next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }

   //将指定元素添加到此列表的结尾。
    public boolean add(E e) {
        Node<E> node = new Node<E>(null, e, null);
        if(tail == null) {//head == tail 是一个空链表
            head = tail = node;
        } else {//非空链表
            Node<E> last = tail;//添加新元素之前的最后一个元素
            last.next = node;
            node.prev = last;
            tail = node;
        }
        size++;
        return true;
    }
    //将指定元素插入此列表的开头。
    public void addFirst(E e) {
        Node<E> node = new Node<E>(null, e, null);
        if(head == null) {
            head = tail = node;
        } else {
            Node<E> first = head;//first是添加新元素之前的head元素，是添加新元素之后的第二个元素(或者说是最新head的next)
            first.prev = node;
            node.next = first;
            head = node;
        }
        size++;
    }

    /**
     * 在此列表中指定的位置插入指定的元素。
     * 思路：关键在于如何定位到索引对应的节点
     *  如果index索引<size的一半儿，说明该节点在列表的前半部分，所以从head找起比较便利
     *  如果index索引>size的一半儿，说明该节点在列表的后半部分，所以从tail找起比较便利
     */
    public void add(int index, E element) {
        Node<E> node = getNode(index);
        Node<E> newNode = new Node<E>(null, element, null);
        //node = head
        if(node == head) {//说明在index=0的位置插入 只需要考虑下一元素即可，因为前驱元素是空
            node.prev = newNode;
            newNode.next = node;
            head = newNode;
        }else {
            newNode.prev = node.prev;
            newNode.prev.next = newNode;
            newNode.next = node;
            newNode.next.prev = newNode;
        }
        size++;
    }

    /**
        添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
     *  被添加的链表bMll(bHead, bTail)
     *  添加的链表mll(head, tail)
     *  head -->node ->bHead-->bTail(tail)
     */
    public boolean addAll(MyLinkedList<E> mll) {
        Node<E> last = tail;
        last.next = mll.head;
        mll.head.prev = last;
        tail = mll.tail;
        size += mll.size;
        return true;
    }

    /**
        添加指定 collection 中的所有元素到此列表的指定位置。
     *  被添加的链表bMll(bHead, bTail)
     *  添加的链表mll(head, tail)
     *  head -->node ->bHead-->bTail -->node -->tail
     */
    public boolean addAll(int index, MyLinkedList<E> mll) {
        Node<E> node = getNode(index);
        //node = head
        if(node == head) {//说明在index=0的位置插入 只需要考虑下一元素即可，因为前驱元素是空
            node.prev = mll.tail;
            mll.tail.next = node;
            head = mll.head;
        }else {
            Node<E> bHead = mll.head;
            Node<E> bTail = mll.tail;

            bHead.prev = node.prev;
            bHead.prev.next = bHead;
            bTail.next = node;
            bTail.next.prev = bTail;
        }
        size += mll.size;
        return true;
    }


//    如果此列表包含指定元素，则返回 true。
    public boolean contains(Object o) {
        return indexOf(o) != -1 ? true : false;
    }
    //返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
    public int indexOf(Object o) {
        Node<E> node = head;
        for (int i = 0; i < size; i++) {
            if(node.data.equals(o)) {
                return i;
            }else {
                node = node.next;
            }
        }
        return -1;
    }
//    返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
    public int lastIndexOf(Object o) {
        Node<E> node = tail;
        for (int i = size - 1; i >= 0; i--) {
            if(node.data.equals(o)) {
                return i;
            }else {
                node = node.prev;
            }
        }
        return -1;
    }

    //移除此列表中指定位置处的元素。
    public E remove(int index) {
        Node<E> node = getNode(index);
        if(index == 0) {
            return removeFirst();
        } else if(index == size - 1) {
            return removeLast();
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }
        return node.data;
    }

    //从此列表中移除首次出现的指定元素（如果存在）。-->从前往后找
    public boolean remove(Object o) {
        int index = indexOf(o);
        E remove = remove(index);
        return remove != null;
    }


    //移除并返回此列表的第一个元素。
    public E removeFirst() {
        if(isEmpty()) {
            return null;
        }
        Node<E> node = head;
        head = node.next;
        if(head != null) {
            head.prev = null;
        }
        size--;
        return node.data;
    }
    //移除并返回此列表的最后一个元素。
    public E removeLast() {
        if(isEmpty()) {
            return null;
        }
        Node<E> node = tail;
        tail = node.prev;
        if(tail != null) {
            tail.next = null;
        }
        size -= 1;
        return node.data;
    }

    public boolean isEmpty() {
        return size == 0;
    }

//    将此列表中指定位置的元素替换为指定的元素。
    public E set(int index, E element) {
        Node<E> node = getNode(index);
        E oldValue = node.data;
        node.data = element;
        return oldValue;
    }
    ///////////////////////////

    //从此列表中移除所有元素。
    public void clear() {
        this.size = 0;
        head = tail = null;
    }

    //返回此列表的第一个元素。
    public E getFirst() {
        return head == null ? null : head.data;
    }

    // 返回此列表的最后一个元素。
    public E getLast() {
        return tail == null ? null : tail.data;
    }


    public int size() {
        return this.size;
    }

    //返回此列表中指定位置处的元素。
    public E get(int index) {
        return getNode(index).data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if(head != null) {//放置空链表而造成的空指针问题
            Node node = head;
            while (node.next != null) {
                sb.append(node.data).append(", ");
                node = node.next;
            }
            //到这里说明什么问题 最后一个元素没有进行提取(最后一个元素就是node)
            if (node != null) {
                sb.append(node.data);
            }
        }
        sb.append("]");

        return sb.toString();
    }

    private void checkIndex(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
    }

    /**
     * 根据索引找到索引对应的节点
     * @param index
     * @return
     */
    private Node<E> getNode(int index) {
        checkIndex(index);
        Node<E> node = null;
        if(index < (size >> 1)) {//在左半部分
            node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            //到这里说明什么问题？ node就是index对应的节点
        } else {
            node = tail;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }
}
